package com.fr.lintcode;

import java.util.Stack;

public class Q229 {

    /*
     * @param stk: an integer stack
     * @return: void
     */
    public void stackSorting(Stack<Integer> stk) {
        // write your code here
    	if(stk == null || stk.size() <= 1){
    		return;
    	}
    	Integer min = null;
    	int size = stk.size();
    	Stack<Integer> tmp = new Stack<>();
    	for(int i = size; i > 0; i --) {
    		while(!tmp.isEmpty()) {
    			stk.push(tmp.pop());
    		}
    		for(int j = i; j > 0; j --) {
    			int t = stk.pop();
    			if(min == null) {
    				min = t;
    			}else if(min > t) {
    				tmp.push(min);
    				min = t;
    			}else {
    				tmp.push(t);
    			}
    		}
    		stk.push(min);
    		min = null;
    	}
    }


}
